#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef pair<ll,int> PII;
const int INF=1e9;
const int N =500007;
struct edge
{
	int y,next;
}e[2*N];
int n,m,link[N],cnt=1,C=0,dfn[N],bel[N],st[N],low[N],sign,top;
int f[N],sum[N],cov[N],p[N][20],d[N],q,cx[N];
int ans,mxp1,mxp2,mx1,mx2,aa,bb,cc,dd;
PII t[4*N];
ll tag[4*N];
ULL val[2*N],s[N];
map<ULL,int> mp1,mp2,mp3;
mt19937_64 rnd(2333);
vector<int> per[N];
void Apply(int x,int y){e[++cnt]={y,link[x]},link[x]=cnt;}
void tarjan(int x,int fr)
{
	dfn[x]=low[x]=++sign,st[++top]=x;
	for(int i=1;i<=18;i++)p[x][i]=p[p[x][i-1]][i-1];
	for(int i=link[x];i;i=e[i].next)
	{
		if((i^1)==fr)continue;
		int y=e[i].y;
		if(!dfn[y])p[y][0]=x,d[y]=d[x]+1,tarjan(y,i),low[x]=min(low[x],low[y]),f[y]=i;
		else 
		{
			low[x]=min(low[x],dfn[y]);
			if(x<y)val[i]=rnd(),mp3[val[i]]=i,s[x]^=val[i],s[y]^=val[i];
		}
	}
	if(low[x]==dfn[x])
	{
		int tmp=0;
		C++;
		while(tmp!=x)tmp=st[top--],bel[tmp]=C;
	}
}
void upd(int w,int a,int b,int c,int d){if(w>ans)ans=w,aa=a,bb=b,cc=c,dd=d;}
int KK,ANS;
void DFS(int x)
{
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(f[y]!=i)continue;
		DFS(y);
		s[x]^=s[y];
		cov[x]+=cov[y];
	}
	if(x!=1&&s[x]==0)
	{
		if(cov[x]>mx1)mx2=mx1,mxp2=mxp1,mx1=cov[x],mxp1=x;
		else if(cov[x]>mx2)mx2=cov[x],mxp2=x;
		ANS=max(ANS,cov[x]);
	}
	if(mp3.count(s[x])) upd(cov[x],x,p[x][0],e[mp3[s[x]]].y,e[mp3[s[x]]^1].y);
	if(s[x]&&!mp2[s[x]])mp2[s[x]]=x;
}
void Push(int p,ll z){tag[p]+=z,t[p].first+=z;}
void Pushdown(int p){if(tag[p])Push(p*2,tag[p]),Push(p*2+1,tag[p]),tag[p]=0;}
void Build(int p,int l,int r){tag[p]=0;if(l==r)return t[p]=PII(-INF,l),void();int mid=(l+r)/2;Build(p*2,l,mid),Build(p*2+1,mid+1,r);t[p]=max(t[p*2],t[p*2+1]);}
int Jump(int x,int y){for(int i=18;i>=0;i--)if(d[x]-(1<<i)>d[y])x=p[x][i];return x;}
void Addate(int p,int l,int r,int x,int y,ll z){if(y<1)return ;if(x<=l&&r<=y)return Push(p,2*z);Pushdown(p);int mid=(l+r)>>1;if(x<=mid)Addate(p*2,l,mid,x,y,z);if(mid<y)Addate(p*2+1,mid+1,r,x,y,z);t[p]=max(t[p*2],t[p*2+1]);}
void Upd(int p,int l,int r,int x,int y){if(x<1)return ;if(l==r)return t[p]=PII(tag[p]+y,l),void();Pushdown(p);int mid=(l+r)>>1;if(x<=mid)Upd(p*2,l,mid,x,y);else Upd(p*2+1,mid+1,r,x,y);t[p]=max(t[p*2],t[p*2+1]);}
PII Query(int p,int l,int r,int x,int y){if(x<=l&&r<=y)return t[p];int mid=(l+r)>>1;Pushdown(p);PII ret=PII(-INF,0);if(x<=mid)ret=max(ret,Query(p*2,l,mid,x,y));if(mid<y)ret=max(ret,Query(p*2+1,mid+1,r,x,y));return ret;}
vector<int> hard_paths[N];
int mindep[N];
void dfs(int x)
{
	st[d[x]]=x;
	Addate(1,1,n,1,d[x]-1,cx[x]);
	for(int y:hard_paths[x])Addate(1,1,n,1,d[y],-1);
	if(s[x])
	{
		PII ret=Query(1,1,n,d[mp1[s[x]]],d[x]);
		if(ret.first>=0)upd(ret.first-cov[x],x,p[x][0],st[ret.second],st[ret.second-1]);
	}
	for(int y:per[x])Addate(1,1,n,1,d[y],-1);
	Upd(1,1,n,d[x],cov[x]);
	if(s[x]&&mp2[s[x]]==x)Addate(1,1,n,d[mp1[s[x]]],d[mp2[s[x]]],-INF);
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(f[y]!=i)continue;
		dfs(y);
	}
	Addate(1,1,n,1,d[x]-1,-cx[x]);
	Upd(1,1,n,d[x],-INF);
	for(int y:per[x])Addate(1,1,n,1,d[y],1);
	if(s[x]&&mp2[s[x]]==x){Addate(1,1,n,d[mp1[s[x]]],d[mp2[s[x]]],INF);}
	for(int y:hard_paths[x])Addate(1,1,n,1,d[y],1);
}
multiset<PII> paths;
void Exdfs(int x)
{
	int son=0;
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(f[y]!=i)continue;
		if(mindep[y]<=d[x])
		{
			son=y;
			continue;
		}
		Exdfs(y);
		while(1)
		{
			auto it=paths.lower_bound(PII(d[x]+1,0));
			if(it==paths.end())break;
			paths.erase(it);
		}
	}
	if(son)
	{
		int de=d[mp1[s[son]]];
		while(1)
		{
			auto it=paths.lower_bound(PII(de,0));
			if(it==paths.end())break;
			if((it->first)>d[x]){paths.erase(it);continue;}
			hard_paths[son].push_back(p[it->second][0]);
			paths.erase(it);
		}
		Exdfs(son);
		while(1)
		{
			auto it=paths.lower_bound(PII(d[x]+1,0));
			if(it==paths.end())break;
			paths.erase(it);
		}
	}
	for(int y:per[x])paths.insert(PII(d[y]+1,Jump(x,y)));
}
void Match(int x)
{
	if(s[x]&&!mp1[s[x]])mp1[s[x]]=x;
	if(s[x])mindep[x]=d[mp1[s[x]]];
	else mindep[x]=1e9;
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(f[y]!=i)continue;
		Match(y);
		mindep[x]=min(mindep[x],mindep[y]);
	}
}
int LCA(int x,int y){
	if(d[x]<d[y])swap(x,y);
	for(int i=18;i>=0;i--)if(d[x]-(1<<i)>=d[y])x=p[x][i];
	if(x==y)return x;
	for(int i=18;i>=0;i--)if(p[x][i]^p[y][i])x=p[x][i],y=p[y][i];
	return p[x][0];
}
void Solve()
{
	scanf("%d%d%d%d",&n,&m,&q,&KK);
	ans=mx1=mx2=-1;
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		Apply(x,y);
		Apply(y,x);
	}
	tarjan(1,0);
	for(int i=1,x,y,z;i<=q;i++)
	{
		scanf("%d%d",&x,&y);
		cov[x]++;cov[y]++;
		cov[z=LCA(x,y)]-=2;
		if(x!=z)per[x].push_back(z),cx[Jump(x,z)]++;
		if(y!=z)per[y].push_back(z),cx[Jump(y,z)]++;
	}
	DFS(1);
	if(KK==1){printf("%d\n",ANS);return;}
	Match(1);Exdfs(1);Build(1,1,n);dfs(1);
	if(mx1+max(mx2,0)>ans) cout<<mx1+max(mx2,0)<<'\n';
	else if(ans!=-1) cout<<ans<<'\n';
	else puts("0");
	for(int i=1;i<=n;i++)
	{
		link[i]=dfn[i]=bel[i]=st[i]=low[i]=cx[i]=f[i]=sum[i]=cov[i]=d[i]=s[i]=0;
		per[i].clear();memset(p[i],0,sizeof(p[i]));
		hard_paths[i].clear();mindep[i]=0;
	}
	paths.clear();
	for(int i=1;i<=cnt;i++)
	e[i]={0,0},val[i]=0;
	cnt=1,C=sign=top=0;
}
int main(){
	freopen("hide.in","r",stdin);
	freopen("hide.out","w",stdout);
	Solve();
	return 0;
}
